home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ftp.cs.arizona.edu
/
ftp.cs.arizona.edu.tar
/
ftp.cs.arizona.edu
/
icon
/
newsgrp
/
group95c.txt
/
000084_icon-group-sender _Sat Nov 18 15:55:45 1995.msg
< prev
next >
Wrap
Internet Message Format
|
1996-01-03
|
6KB
Received: by cheltenham.cs.arizona.edu; Wed, 22 Nov 1995 10:44:02 MST
To: icon-group@cs.arizona.edu
Date: 18 Nov 1995 15:55:45 +0100
From: janpeter@mpi.nl (Jan-Peter de Ruiter)
Message-Id: <qjraz6dlam.fsf_-_@mpih16.mpi.nl>
Organization: Max-Panck Institut f|r Psycholinguistik, Nijmegen, the Netherlands
Sender: icon-group-request@cs.arizona.edu
References: <485l4c$erl@newshost.nmt.edu>
Subject: Mathematical sets in Icon (Re: Comparing sets for equality)
Errors-To: icon-group-errors@cs.arizona.edu
In article <485l4c$erl@newshost.nmt.edu> john@nmt.edu (John Shipman) writes:
I need an Icon function to test two sets to see if they're identical.
Is there an operator that does this, that I have somehow missed?
No, this is a problem. A few years ago we discussed this problem here
too, and Icon's definition of identical is not the mathematical
definition, because implementing it in the mathematically correct way
will decrease Icon's performance, if I remember correctly.
Your solution will only work partially. If you insert the same string
twice, Icon will think there's two elements in your set, which is not
the way it should work, if you think of sets as mathematical sets.
Here's a complete implementation that I wrote to solve this problem.
It can also be used to check if two Icon values are identical in the
sense that they have the same values (not that they refer to the same
objects). If there's anyone from the Icon project who likes to put
this extension in the IPL, please be my guest.
Greetings,
Jan
#############################################################################
# MSET LIBRARY #
# #
# by Jan P. de Ruiter, 1992 #
# Public domain software. #
# #
# Implements the "mset" type. #
# #
# The idea of the mset type is that no two identical data-structures can be #
# present in a set, where identity is defined as "containing the same #
# elements". #
# #
# This seemingly radical idea is actually quite common in mathematics. :-) #
# #
# Definitions implicit in the procedure same_value(..,..): #
# #
# TYPE IDENTITY TEST #
# #
# all types === and if this test fails... #
# #
# integer = #
# real = #
# cset, string == #
# record all fields have same value #
# list all elements are the same, and the ordering is the same #
# table same keys, and every key has the same associated value #
# set contain the same elements #
# #
#############################################################################
#
# This is the core routine.
# It succeeds if two things have the same value(s).
#
procedure same_value(d1,d2)
if d1 === d2 then return # same object
else
if type(d1) ~== type(d2) then fail # not the same type
else
if *d1 ~= *d2 then fail # not the same size
else
case type(d1) of { # the same type and size
("set" | "table" ) : return same_elements(sort(d1,1),sort(d2,1))
("list") : return same_elements(d1,d2)
("real" | "integer") : return(d1 = d2)
("cset" | "string" ) : return(d1 == d2)
default : return same_elements(d1,d2) # user defined type
}
end
#
# used in same_value:
#
procedure same_elements(l1,l2)
if l1 === l2 then return # same objects
else
if *l1 ~= *l2 then fail # not the same size
else {
if *l1 = 0 then return # both lists empty
else {
every(i := 1 to *l1) do
if not same_value(l1[i],l2[i]) then fail # recursion
return
}
}
end
#
# The new insert operation. Insert2 always succeeds
#
procedure insert2(S,el)
if same_value(el,!S) then return
return insert(S,el)
end
#
# The new member operation, that also detects equal-valued elements
#
procedure member2(S,el)
if same_value(!S,el) then return
fail
end
#
# The new delete operation, that detects equal-valued elements.
# Always succeeds
#
procedure delete2(S,el)
every(t := !S) do if same_value(t,el) then return delete(S,t)
return
end
#
# conversion of standard icon set into new mset.
#
procedure reduce(iset)
temp := set()
every(insert2(temp,!iset))
return temp
end